package tree.binarysearchtree;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname : TwoSumIVInputIsABST
 * @Description :
 * <a href="https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/">653. 两数之和 IV - 输入二叉搜索树</a>
 * @Author : chentianyu
 * @Date 2023/1/29 14:53
 */


public class TwoSumIVInputIsABST {
    public boolean findTarget(TreeNode root, int k) {
        // 获取BST中序遍历列表（升序）
        List<Integer> inorder = new ArrayList<>();
        inorder(root, inorder);
        // 双指针查询目标元素
        int left = 0, right = inorder.size() - 1;
        while (left < right) {
            if (inorder.get(left) + inorder.get(right) > k) right--;
            else if (inorder.get(left) + inorder.get(right) < k) left++;
            else return true;
        }
        return false;
    }

    private void inorder(TreeNode root, List<Integer> inorder) {
        if (root == null) return ;

        inorder(root.left, inorder);
        inorder.add(root.val);
        inorder(root.right, inorder);
    }
}
